package org.example.algorithm.dichotomy;

public class MySqrtSolution {
    public static void main(String[] args) {
        MySqrtSolution solution = new MySqrtSolution();
        int ans = solution.mySqrt(2147395599);
        System.out.println(ans);
    }


    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int left = 0;
        int right = x;
        while (left <= right) {
            int middle = (right - left) / 2 + left;
            long temp = (long) middle * middle;
            if (temp == x) {
                return middle;
            } else if (temp > x) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return right;
    }
}
